Key Concepts Explained
To understand the timeline, we use two timestamps for each vertex v:
- d[v] (Discovery Time): The moment we first visit a vertex. Think of this as "starting a task."
- f[v] (Finish Time): The moment after we have explored all of its descendants. This means "the task and all its sub-tasks are complete."
The animation shows how the interval [d[v], f[v]] for a child node is always nested inside its parent's interval. This is the parenthesis structure, and it's useful for detecting cycles and creating topological sorts.
| v | d[v] | f[v] |
|---|---|---|
| A | 1 | 12 |
| C | 2 | 5 |
| E | 3 | 4 |
| B | 6 | 11 |
| D | 7 | 10 |
| F | 8 | 9 |